package LeetCode.exercise;

import java.util.Arrays;
import java.util.List;

public class LC315 {
    public static void main(String[] args) {
        LC315 l = new LC315();
        int[] arr = {5,2,6,1};
        List<Integer> list = l.countSmaller(arr);
        System.out.println(list);
    }
    int[] tmp1;
    int[] tmp2;
    public List<Integer> countSmaller(int[] nums) {

        tmp1 = new int[nums.length];
        tmp2 = new int[nums.length];
        int[] res = new int[nums.length];
        int[] index = new int[nums.length];
        for(int i = 0; i < index.length; i++){
            index[i] = i;
        }
        res =  merge(nums, 0, nums.length-1, index, res);
        List<int[]> list = Arrays.asList(res, new int[] {12});
        System.out.println(list.get(0).length);
        System.out.println(list.size());
        return null;
    }
    public int[] merge(int[] nums, int left, int right, int[] index, int[] res){
        if(left >= right){
            return res;
        }
        int mid = (right + left) / 2;
        res = merge(nums, left, mid, index, res);
        res = merge(nums, mid + 1, right, index, res);
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] <= nums[cur2]){
                tmp1[i] = nums[cur2];
                tmp2[i++] = index[cur2++];
            } else {
                res[index[cur1]] += right - cur2 + 1;
                tmp1[i] = nums[cur1];
                tmp2[i++] = index[cur1++];
            }
        }
        while(cur1 <= mid){
            tmp1[i] = nums[cur1];
            tmp2[i++] = index[cur1++];
        }
        while(cur2 <= right){
            tmp1[i] = nums[cur2];
            tmp2[i++] = index[cur2++];
        }
        for(int j = left; j <= right; j++){
            nums[j] = tmp1[j-left];
            index[j] = tmp2[j-left];
        }
        return res;
    }
}
